class Solution {
public:
    int majorityElement(vector<int>& nums) 
    {
        int ret = nums[0];
        int max_cnt = 1;
        for(int i = 1;i<nums.size();i++)
        {
            if(nums[i] == ret)
            {
                max_cnt++;
            }
            else
            {
                max_cnt--;
                if(max_cnt == 0)
                {
                    max_cnt = 1;
                    ret = nums[i];
                }
            }
        }
        return ret;    
    }
};